Publication Details
Scott Pardue, Nikos Chrisochoides and Andrey Chernikov.
Published in Modeling, Simulation, and Visualization Student Capstone Conference, April, 2015
Abstract
Computing the Euclidean Distance Transform (EDT) for binary images is an important problem with applications involving medical image processing, computer vision, computational geometry, and pattern recognition. In algorithm development, execution time is an important factor. Parallel algorithm development also needs to focus on scalability and efficiency. Currently, there exists a sequential algorithm of O(n) complexity developed by Maurer et al. and a parallel implementation of Maurer's algorithm developed by Staubs et al. with an asymptotical speedup of 3 times. In this paper, we present a parallel implementation of Maurer's algorithm with a theoretical complexity of O(n/p) for n voxels and p threads and an evaluated unprecedented linear speedup for large datasets.
